package com.yangzhe.algorithm.c038;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的组合
// 答案 不能 包含重复的组合。返回的答案中，组合可以按 任意顺序 排列
// 注意其实要求返回的不是子集，因为子集一定是不包含相同元素的，要返回的其实是不重复的组合
// 比如输入：nums = [1,2,2]
// 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
// 测试链接 : https://leetcode.cn/problems/subsets-ii/
public class Code02_Combinations {

    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 1};
        List<List<Integer>> lists = subsetsWithDup(nums);

        for (List<Integer> list : lists) {
            System.out.print("[");
            for (Integer i : list) {
                System.out.print(i + ",");
            }
            System.out.print("]");
            System.out.println();
        }
    }

    /**
     * 思路：递归
     * 1. 排序数组
     * 2. 当前位置i数字要1个，其他递归， 当前位置i要2个，其他递归.....
     *
     * @param nums 未排序的数组
     * @return
     */
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();

        // 排序
        Arrays.sort(nums);

        subList(nums, 0, new int[nums.length], 0, result);

        return result;
    }

    /**
     * @param nums   排序后的数组
     * @param i      当前递归到的位置
     * @param path   缓存的子数组
     * @param size   利用方法栈记住原始类型的特性，递归中可以回溯到之前的数组的状态
     * @param result 最终结果
     */
    public static void subList(int[] nums, int i, int[] path, int size, List<List<Integer>> result) {
        if (i == nums.length) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < size; j++) {
                int num = path[j];
                list.add(num);
            }
            result.add(list);
        } else {
            // 当前数组有几个
            int count = 0;
            int num = nums[i];
            while (i + count < nums.length && nums[i + count] == num) {
                count++;
            }

            // 下一个数字起始位置
            int nextNumIndex = i + count;

            // 不要当前数字
            subList(nums, nextNumIndex, path, size, result);

            // 当前数组要1,2,3个....
            for (; count > 0; count--) {
                path[size++] = num;
                subList(nums, nextNumIndex, path, size, result);
            }
        }
    }

}
